#ifndef xpack_draft_hashmap
#define xpack_draft_hashmap
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::draft_hashmap::inc
#include"define/nullref.hpp"
#include"dumb/move.hpp"
#include"macro/xnew.hpp"
#include"macro/xdefer.hpp"
#include"macro/xexport.hpp"
#include"macro/xstruct.hpp"
#include"memop/cmp.hpp"
#include"utils/bits_indicator.hpp"
#pragma pop_macro("xuser")

namespace mixc::draft_hashmap::origin{
    template<class key_t, class val_t>
    xstruct(
        xtmpl(hashnode, key_t, val_t),
        xpubf(m_key,    key_t),
        xpubf(m_val,    val_t),
        xpubf(m_next,   hashnode<key_t, val_t> *)
    )
        hashnode(key_t const & key, val_t const & val, hashnode<key_t, val_t> * next) : 
            m_key(key),
            m_val(val),
            m_next(next) {
        }
    $

    template<class key_t, class val_t>
    xstruct(
        xtmpl(hashmap_data, key_t, val_t),
        xpubf(m_lines,  uxx),
        xpubf(m_moved,  uxx),
        xpubf(m_count,  uxx),
        xpubf(m_a,      hashnode<key_t, val_t>  **),
        xpubf(m_b,      hashnode<key_t, val_t>  **),
        xpubf(m_bmp_a,  inc::bits_indicator<>),
        xpubf(m_bmp_b,  inc::bits_indicator<>)
    ) $

    template<class key_t, class val_t>
    struct hashmap_helper{
        static constexpr uxx step_multiple      = 2;
        static constexpr uxx init_list_length   = 16;

        using hashmap_t     = hashmap_data<key_t, val_t>;
        using the_t         = hashmap_helper<key_t, val_t>;
        using node          = hashnode<key_t, val_t>;
        using nodep         = node *;
        using nodepp        = node **;

        template<class hash_invoke_t>
        static auto addressing(hashmap_t & map, hash_invoke_t const & hash, key_t const & value){
            struct {
                uxx     i_a;
                uxx     i_b;
                uxx     hash;
            } result;

            auto mask                       = map.m_lines - 1;
            result.hash                     = hash(value);
            result.i_a                      = result.hash & (mask);
            result.i_b                      = result.hash & (mask >> 1);
            return result;
        }

        template<class hash_invoke_t, class free_invoke_t>
        static void adjust(hashmap_t & map, hash_invoke_t const & hash, free_invoke_t const & free){
            if (auto i = map.m_moved++; i * the_t::step_multiple >= map.m_lines){
                return;
            }
            else{
                for(auto head = map.m_b[i]; head != nullptr;){
                    auto current            = head;
                    auto next               = current->m_next;
                    auto address            = the_t::addressing(map, hash, current->m_key);
                    auto i_hash             = address.i_a;
                    
                    // 放置到新的 hashmap 列表中
                    current->m_next         = map.m_a[i_hash] == nullptr ? nullptr : map.m_a[i_hash];
                    head                    = next;
                    map.m_a[i_hash]         = current;
                    map.m_bmp_a.set(i_hash);
                }

                if (map.m_moved * the_t::step_multiple == map.m_lines){
                    // map.m_b 和 map.m_bmp_b 共用一块内存，分前后两段
                    free(map.m_b, sizeof(map.m_b[0]) * map.m_lines / the_t::step_multiple + map.m_bmp_b.cost_bytes());
                    map.m_b                 = nullptr;
                }
                else{
                    map.m_b[i]              = nullptr;
                    map.m_bmp_b.reset(i);
                }
            }
        }

        template<class alloc_invoke_t>
        static void new_lines(hashmap_t & map, alloc_invoke_t const & alloc){
            // 分配新的 map.m_bmp_a
            xnew(& map.m_bmp_a) inc::bits_indicator<>(map.m_lines, [&](uxx length) -> uxxp {
                auto line_bytes         = map.m_lines * sizeof(map.m_a[0]);
                auto total_bytes        = line_bytes + length * sizeof(uxx);
                auto mem                = alloc(total_bytes);

                // 前半部分内存
                map.m_a                 = nodepp(mem);

                // 后半部分内存用作 bmp
                return uxxp(u08p(mem) + line_bytes);
            });
        }
    };

    template<class key_t, class val_t>
    struct hashmap{
    private:
        using helper        = hashmap_helper<key_t, val_t>;
        using hashmap_t     = hashmap_data<key_t, val_t>;
        using node          = hashnode<key_t, val_t>;
        using nodep         = node *;
        using nodepp        = node **;
        using the_t         = hashmap<key_t, val_t>;
    public:
        template<class alloc_invoke_t>
        static void init(hashmap_t & map, alloc_invoke_t const & alloc){
            map.m_lines                     = helper::init_list_length;
            map.m_moved                     = map.m_lines;
            map.m_count                     = 0;
            map.m_b                         = nullptr;
            helper::new_lines(map, alloc);
        }

        template<class hash_invoke_t, class alloc_invoke_t, class free_invoke_t>
        static void set(
            hashmap_t                 & map, 
            hash_invoke_t       const & hash, 
            alloc_invoke_t      const & alloc,
            free_invoke_t       const & free, 
            key_t               const & key, 
            val_t               const & val
        ){
            // 先 adjust
            helper::adjust(map, hash, free);

            auto address                    = helper::addressing(map, hash, key);
            auto i_hash                     = address.i_a;
            auto i_hash_old                 = address.i_b;
            auto current                    = map.m_bmp_a.get(i_hash) ? map.m_a[i_hash] : map.m_a[i_hash] = nullptr;
            auto need_create_new            = true;

            // 在新列表中寻找
            for(; current != nullptr; current = current->m_next){
                if (inc::cmp(current->m_key, key) == 0){
                    current->m_val          = val;
                    return;
                }
            }

            xdefer{
                if (need_create_new == false){
                    return;
                }

                auto new_node               = xnew(alloc(sizeof(node))) node(key, val, map.m_a[i_hash]);
                map.m_a[i_hash]             = new_node;
                map.m_count                += 1;
                map.m_bmp_a.set(i_hash);

                if (map.m_count != map.m_lines){
                    return;
                }

                map.m_lines                *= 2;
                map.m_moved                 = 0;
                map.m_b                     = map.m_a;

                // 将 map.m_bmp_a 转移到 map.m_bmp_b
                xnew(& map.m_bmp_b) inc::bits_indicator<>(inc::move(map.m_bmp_a));

                // 再创建新的 map.m_a、map.m_bmp_a
                helper::new_lines(map, alloc);
            };

            // 如果已经转移到新的 hashmap 列表，就直接在新列表的槽中新建节点
            if (map.m_moved > i_hash_old){
                return;
            }

            // 在旧列表中寻找
            for(current = map.m_bmp_b.get(i_hash_old) ? map.m_b[i_hash_old] : nullptr; 
                current != nullptr; 
                current = current->m_next
            ){
                if (inc::cmp(current->m_key, key) == 0){
                    current->m_val          = val;
                    need_create_new         = false;
                    return;
                }
            }
        }

        template<class hash_invoke_t, class alloc_invoke_t, class free_invoke_t>
        static val_t & get(
            hashmap_t                 & map, 
            hash_invoke_t       const & hash, 
            alloc_invoke_t      const & alloc,
            free_invoke_t       const & free, 
            key_t               const & key
        ){
            helper::adjust(map, hash, free);

            auto address                    = helper::addressing(map, hash, key);
            auto i_hash                     = address.i_a;
            auto i_hash_old                 = address.i_b;
            auto current                    = map.m_bmp_a.get(i_hash) ? map.m_a[i_hash] : nullptr;

            // 在新列表中寻找
            for(; current != nullptr; current = current->m_next){
                if (inc::cmp(current->m_key, key) == 0){
                    return current->m_val;
                }
            }

            // 如果已经转移到新的 hashmap 列表，就直接在新列表的槽中新建节点
            if (map.m_moved > i_hash_old){
                return inc::nullref;
            }

            // 在旧列表中寻找
            for(current = map.m_bmp_b.get(i_hash_old) ? map.m_b[i_hash_old] : nullptr; 
                current != nullptr; 
                current = current->m_next
            ){
                if (inc::cmp(current->m_key, key) == 0){
                    return current->m_val;
                }
            }

            return inc::nullref;
        }

        template<class hash_invoke_t, class alloc_invoke_t, class free_invoke_t>
        static void talk_out(
            hashmap_t                 & map, 
            hash_invoke_t       const & hash, 
            alloc_invoke_t      const & alloc,
            free_invoke_t       const & free, 
            key_t               const & key,
            val_t                     * val
        ){

            struct meta{
                nodep                 & head;
                inc::bits_indicator<> & bmp;
                uxx                     i;
            };

            helper::adjust(map, hash, free);

            auto address                    = helper::addressing(map, hash, key);
            meta pairs[]                    = { 
                meta{ map.m_a[address.i_a], map.m_bmp_a, address.i_a },
                meta{ map.m_b[address.i_b], map.m_bmp_b, address.i_b },
            };

            // 在新列表中寻找
            for(meta & item : pairs){
                auto current                = item.head;
                auto p_prev                 = & item.head;

                for(; current != nullptr; p_prev = & current->m_next, current = current->m_next){
                    if (inc::cmp(current->m_key, key) == 0){
                        if (val != nullptr){
                            val[0]          = current->m_val;
                        }

                        map.m_count        -= 1;
                        p_prev[0]           = current->m_next;
                        current->~node();
                        free(current, sizeof(*current));

                        if (item.head == nullptr){
                            map.m_bmp_a.reset(item.i);
                        }
                        return;
                    }
                }
            }
        }

        template<class hash_invoke_t, class alloc_invoke_t, class free_invoke_t>
        static void remove(
            hashmap_t                 & map, 
            hash_invoke_t       const & hash, 
            alloc_invoke_t      const & alloc,
            free_invoke_t       const & free, 
            key_t               const & key
        ){
            the_t::talk_out(map, hash, alloc, free, key, nullptr);
        }

        template<class free_invoke_t>
        static void clear(hashmap_t & map, free_invoke_t const & free){
            struct meta{
                nodepp                  list;
                inc::bits_indicator<> & bmp;
            };

            auto lists                  = { 
                meta{ map.m_a, map.m_bmp_a }, 
                meta{ map.m_b, map.m_bmp_b },
            };

            for(meta & item : lists){
                if (item.list == nullptr){
                    continue;
                }

                for(auto i = item.bmp.pop_first(); i != not_exist; item.bmp.pop_first()){
                    for(auto current = map.m_a[i]; current != nullptr;){
                        auto next       = current->m_next;
                        current->~node();
                        free(current, sizeof(*current));
                        current         = next;
                    }

                    map.m_a[i]          = nullptr;
                }
            }

            if (map.m_b != nullptr){
                free(map.m_b, sizeof(map.m_b[0]) * map.m_lines / helper::step_multiple + map.m_bmp_b.cost_bytes());
                map.m_b                 = nullptr;
            }
            map.m_moved                 = map.m_lines / helper::step_multiple;
        }
    };
}

#endif

xexport_space(mixc::draft_hashmap::origin)
